package com.yubest;

/**
 * 给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
 * <p>
 * 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
 * <p>
 * 请你返回乘积为正数的最长子数组长度。
 * <p>
 *  
 * <p>
 * 示例  1：
 * <p>
 * 输入：nums = [1,-2,-3,4]
 * 输出：4
 * 解释：数组本身乘积就是正数，值为 24 。
 * 示例 2：
 * <p>
 * 输入：nums = [0,1,-2,-3,-4]
 * 输出：3
 * 解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
 * 注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
 * 示例 3：
 * <p>
 * 输入：nums = [-1,-2,-3,0,1]
 * 输出：2
 * 解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
 * 示例 4：
 * <p>
 * 输入：nums = [-1,2]
 * 输出：1
 * 示例 5：
 * <p>
 * 输入：nums = [1,2,3,5,-6,4,0,10]
 * 输出：4
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/12/29 12:10
 */
public class P1567 {

    public static void main(String[] args) {
        new Solution1567().getMaxLen(new int[]{-1, -2, -3, 0, 1});
    }
}

class Solution1567 {

    /**
     * 思路：动态规划
     * <p>
     * 可以使用动态规划得到乘积为正数的最长子数组长度。定义两个数组 positive 和 negative，其中 positive[i] 表示以下标 i 结尾的乘积为正数的最长子数组长度，negative[i] 表示乘积为负数的最长子数组长度。
     * <p>
     * 当 i=0 时，以下标 i 结尾的子数组的长度为 1，因此当 nums[0]>0 时 positive[0]=1，当 nums[0]<0 时 negative[0]=1。
     * <p>
     * 当 i>1 时，根据 nums[i] 的值计算 positive[i] 和 negative[i] 的值。
     * <p>
     * 当 nums[i]>0 时，之前的乘积乘以 nums[i] 不会改变乘积的正负性。
     * <p>
     * positive[i] 的计算为：positive[i]=positive[i−1]+1
     * <p>
     * negative[i] 的计算为：
     * 当negative[i-1]>0时，negative[i] = negative[i-1]+1
     * 当negative[i-1]=0时，negative[i] = 0
     * <p>
     * 这是因为当 negative[i−1]=0 时，negative[i] 本身无法形成一个乘积为正数的子数组，所以要特殊判断。
     * <p>
     * 当 nums[i]<0 时，之前的乘积乘以 nums[i] 会改变乘积的正负性。
     * <p>
     * positive[i] 的计算为：
     * 当negative[i-1]>0时，positive[i] = negative[i-1]+1
     * 当negative[i-1]=0时，positive[i] = 0
     * <p>
     * 这是因为当 negative[i−1]=0 时，positive[i] 本身无法形成一个乘积为负数的子数组，所以要特殊判断。
     * <p>
     * negative[i] 的计算为：negative[i]=positive[i−1]+1
     * <p>
     * 当 nums[i]=0 时，以下标 i 结尾的子数组的元素乘积一定为 0，因此有 positive[i]=0 和 negative[i]=0。
     * <p>
     * 在计算 positive 和 negative 两个数组的过程中维护乘积为正数的最长子数组长度，当遍历结束时，即可得到最长子数组长度。
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/solution/cheng-ji-wei-zheng-shu-de-zui-chang-zi-shu-zu-ch-3/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int curPos = 0, curNeg = 0, prePos = 0, preNeg = 0;
        if (nums[0] > 0) {
            prePos = 1;
        } else if (nums[0] < 0) {
            preNeg = 1;
        }
        int max = prePos;
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0) {
                curPos = prePos + 1;
                if (preNeg > 0) {
                    curNeg = preNeg + 1;
                }
            } else if (nums[i] < 0) {
                if (preNeg > 0) {
                    curPos = preNeg + 1;
                } else {
                    curPos = 0;
                }
                curNeg = prePos + 1;
            } else {
                curPos = 0;
                curNeg = 0;
            }
            prePos = curPos;
            preNeg = curNeg;
            max = Math.max(max, curPos);
        }
        return max;
    }
}
